Fourier analysis is a family of mathematical techniques based on decomposing signals into sinusoids. The discrete Fourier transform (“DFT”) is the family member that can be used with digital signals and digital signal processing. A DFT can decompose a sequence or set of data values into components of different frequencies. In calculating each of the components (real and imaginary pairs) of the Fourier transform, one must use all N vectors of the sampled set. As is known in the art, the total computation time of the DFT is the total number of operations N×N, or N2. While the DFT is useful in many fields, computing it directly from the definition can often be too slow to be practical.
A fast Fourier transform (“FFT”) is a way to compute the same result as the DFT, more quickly. Through the use of interlace decomposition, an FFT can compute approximately the same result as the DFT in N log N operations. Still this number of computations can often be slow and take up large amounts of processing time. A need exists to overcome the deficiencies of the DFT and the FFT.